package com.zjsru.plan2024.normal;

import java.util.ArrayList;
import java.util.List;

/**
 * 3211. 生成不含相邻零的二进制字符串
 *
 * @Author: cookLee
 * @Date: 2024-10-29
 */
public class ValidStrings {

    /**
     * 主
     * \
     * 输入： n = 3
     * 输出： ["010","011","101","110","111"]
     * 解释：
     * 长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。
     * \
     * 输入： n = 1
     * 输出： ["0","1"]
     * 解释：
     * 长度为 1 的有效字符串有："0" 和 "1"。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        ValidStrings validStrings = new ValidStrings();
        int n = 3;
        System.out.println(validStrings.validStrings(n));
    }

    List<String> res = new ArrayList<>();

    int n;

    /**
     * 有效字符串
     *
     * @param n n
     * @return {@link List}<{@link String}>
     */
    public List<String> validStrings(int n) {
        this.n = n;
        this.dfs(new StringBuilder());
        return this.res;
    }

    /**
     * dfs
     *
     * @param sb 字符串生成器
     */
    private void dfs(StringBuilder sb) {
        //符合条件就加入
        if (sb.length() == this.n) {
            this.res.add(sb.toString());
        } else {
            //处理添加0的情况
            if (sb.toString().isEmpty() || sb.charAt(sb.length() - 1) == '1') {
                sb.append(0);
                this.dfs(sb);
                //结束后减去添加位
                sb.setLength(sb.length() - 1);
            }
            //处理添加1的情况
            sb.append(1);
            this.dfs(sb);
            sb.setLength(sb.length() - 1);
        }
    }
}
